# -*- coding: utf-8 -*-
"""
@Time    : 2024/9/6 11:32 
@Author  : ZhangShenao 
@File    : 4.斐波那契数列.py 
@Desc    : 斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列
是意大利数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)在《计算之书》中提出一个在理想假设条件下兔子成长率的问题而引入的数列
所以这个数列也被戏称为兔子数列
斐波那契数列的特点是数列的前两个数都是1,从第三个数开始,每个数都是它前面两个数的和,形如:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
斐波那契数列在现代物理、准晶体结构、化学等领域都有直接的应用
"""

# 构造缓存,减少重复计算
cache: dict[int, int] = {}


# 定义斐波那契函数
def fib(n: int) -> int:
    """获取第n个斐波那契数"""

    if n <= 0:
        raise ValueError("n must be positive")

    # 数列的前两个数均为1
    if n == 1 or n == 2:
        return 1

    # 如果缓存中存在,则直接返回
    if n in cache:
        return cache.get(n)

    # 缓存中不存在,利用斐波那契数列的性质,递归计算
    f = fib(n - 1) + fib(n - 2)

    # 将计算结果保存到缓存中
    cache[n] = f

    return f


def fib_seq(n: int) -> list[int]:
    """获取1~n的斐波那契数列"""

    # 输入校验
    if n <= 0:
        raise ValueError("n must be positive")

    # 返回斐波那契数列
    return [fib(i) for i in range(1, n + 1)]


if __name__ == '__main__':
    print(fib_seq(20))
